\documentclass[11pt,twoside,a4paper]{article}

\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
%\usepackage{algorithmic}
%\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_{K}}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\Nm}{\mathcal{N}_{\K/\Q}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{Personal statement}
\author{Jean-Fran\c{c}ois Biasse \\
biasse@lix.polytechnique.fr}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières



\section{Introduction}

%J'ai effectué des travaux de recherche en théorie algorithmique des nombres et en calcul formel. Je 
%e suis aussi intéressé aux applications de ces disciplines à la cryptologie et à la théorie des 
%codes.
During my past research, I worked on algorithmic number theory and on computer algebra. I also focused on the applications 
of these domains to cryptology and number theory.

%Durant ma thèse effectuée à l'École Polytechnique sous la direction d'Andreas Enge, je me suis focalisé 
%sur le calcul du groupe de classes et du groupe des unités d'un corps de nombres. C'est une tâche majeure 
%en théorie algorithmique des nombres, intervenant notamment lors de la résolution d'équations 
%Diopthantiennes. J'ai aussi appliqué certains résultats au calcul du logarithme discret et au calcul 
%d'infrastructure dans les corps de nombres quadratiques, faisant ainsi le lien entre ce domaine et 
%la cryptologie.
During my PhD thesis done at the \'{E}cole polytechnique under the supervision of Andreas Enge, I focused 
on class group and unit group computation of a number field. It is a major task in computational number 
theory, ocurring in particular during the resolution of Diophantine equations. I also applied certain 
results to discrete logarithm and infrastructure computation in quadratic number fields, thus making 
a link between this domain and cryptology.

%J'ai ensuite effectué un premier postdoc au département de mathématiques de l'université de Sydney dans 
%le groupe de développement du logiciel de calcul formel Magma. J'ai eu l'opportunité d'approfondir les 
%sujets de ma thèse, en généralisant les méthodes utilisées pour le calcul du groupe de classes de corps 
%quadratiques aux corps de nombres de degré arbitraire. Les méthodes employées sont inspirées du crible 
%algébrique qui est le meilleur algorithme de factorisation de grands entiers. 
Then, I did a first postdoc at the department of mathematics of the University of Sydney in the Magma 
development team. I had the opportunity to go further into my phd thesis' subject by generalizing the 
methods used for computing the class group of quadratic number fields to number fields of arbitrary 
degree. The methods I used were inspired from the number field sieve, which is the fastest algorithm 
for factoring large integers. 


%Lors de mon deuxième postdoc, débuté en avril 2011 à l'université de Calgary, j'ai souhaité élargir 
%mes domaines de recherche. Je me suis ainsi tourné vers le calcul formel et les mises sous forme canonique 
%de matrices. Je me suis tout d'abord intéressé aux matrices sur $\Z$, et en particulier à la forme normale 
%de Hermite qui joue un rôle particulier lors du calcul du groupe de classes d'idéaux d'un corps de nombres. 
%J'ai ensuite généralisé des résultats obtenus sur $\Z$ aux modules sur l'anneau des entiers $\OK$ d'un corps
%de nombres $K$. La mise sous forme de Hermite d'une base d'un $\OK$-module a des applications en cryptologie
%basées sur les réseaux. J'ai aussi eu l'occasion d'appliquer ces résultats à la théorie des codes, et plus 
%particulièrement au décodage en liste de codes basés sur les corps de nomnbres. 
During my second postdoc, started in April 2011 at the University of Calgary, I prefered to enlarge the scope 
of my research. Therefore, I turned to computer algebra and computations of canonical form computation of matrices. 
I worked first on matrices over $\Z$, and in particular on the Hermite Normal Form which plays a particular role 
during the computation of the ideal class group of a number field. Then I generalized the results obtained over 
$\Z$ to modules over the ring of integers $\OK$ of a number field $K$. The computation of a Hermite Normal Form 
of a basis of an $\OK$-module has applications in lattice-based cryptology. I also had the opportunity to apply these 
results to coding theory, and more particularily list decoding of number field codes.
%permet notamment d'exhiber des arguments numériques en faveur de conjectures ouvertes comme les heuristiques de Cohen-Lenstra~\cite{lenstra_heuristic} sur le groupe de classes d'un corps de nombres quadratiques, les bornes de Littlewood~\cite{littlewood} sur $L(1,\chi)$, ou encore la borne de Bach~\cite{bach} sur la borne minimale $B$ assurant que les idéaux de norme bornée par $B$ engendrent le groupe de classes d'idéaux. Ces méthodes servent aussi à la résolution d'équations diophantiennes : par exemple, le calcul de l'unité fondamentale d'un corps quadratique réel permet le calcul des solutions de l'équation de Pell
%$$T^2 - \Delta U^2 = 1,\ \ T,U\in\Z,$$ 
%associée au discriminant $\Delta$ du corps en question (voir \cite{pell_book}). D'autres équations diophantiennes telles que l'équation de Sch\"{a}ffer
%$$y^2=1^k+2^k+\hdots + (x-1)^k,\ \ k\geq 2,$$ 
%se résolvent à partir de l'équation de Pell~\cite{shaffer}, qui est elle-même un cas particulier des équations aux normes de la forme
%$$\mathcal{N}(\alpha) = 1.$$

%Le calcul de la structure de groupes tels que le groupe de classes d'idéaux d'un corps de nombres est intimement lié aux algorithmes de résolution du logarithme discret, qui est un problème de théorie des nombres à la base de nombreux cryptosystèmes à clef publique. Les stratégies employées pour résoudre ce problème dans le groupe de classes d'idéaux sont les même que pour les corps finis et les jacobiennes de courbes hyperelliptiques, ce qui rend son étude intéressante d'un point de vue cryptographique.

\section{Algorithmic number theory}

%Le calcul du groupe de classes d'idéaux $\cl(\OK)$ d'un corps de nombres $K$ permet notamment d'exhiber des arguments numériques 
%en faveur de conjectures ouvertes comme les heuristiques de Cohen-Lenstra~\cite{lenstra_heuristic} sur le groupe de classes 
%d'un corps de nombres quadratiques, les bornes de Littlewood~\cite{littlewood} sur $L(1,\chi)$, ou encore la borne de 
%Bach~\cite{bach} sur la borne minimale $B$ assurant que les idéaux de norme bornée par $B$ engendrent le groupe de classes 
%d'idéaux. Ces méthodes servent aussi à la résolution d'équations diophantiennes : par exemple, le calcul de l'unité 
%fondamentale d'un corps quadratique réel permet le calcul des solutions de l'équation de Pell
%$$T^2 - \Delta U^2 = 1,\ \ T,U\in\Z,$$ 
%associée au discriminant $\Delta$ du corps en question (voir \cite{pell_book}). D'autres équations diophantiennes telles 
%que l'équation de Sch\"{a}ffer
%$$y^2=1^k+2^k+\hdots + (x-1)^k,\ \ k\geq 2,$$ 
%se résolvent à partir de l'équation de Pell~\cite{shaffer}, qui est elle-même un cas particulier des équations aux normes de 
%la forme
%$$\mathcal{N}(\alpha) = 1.$$
The computation of the ideal class group $\Cl(\OK)$ of a number field $K$ allows in particular to provide numerical evidence 
in favor of unproven conjectures such as the heuristics of Cohen and Lenstra~\cite{lenstra_heuristic} on the ideal class group 
of a quadratic number field, Littlewood's bounds~\cite{littlewood} on $L(1,\chi)$, or Bach's bound on the minimal bound $B$ such 
that ideals of norm lower than $B$ generate the ideal class group. These methods can also be used to solve Diophantine equations. 
For example, the computation of the fundamental unit of a number field allows to solve the Pell equation 
$$T^2 - \Delta U^2 = 1,\ \ T,U\in\Z,$$
associated to the discriminant $\Delta$ of the field in question (see~\cite{pell_book}). Other Diophantine equations such as 
Sch\"{a}ffer equation
$$y^2=1^k+2^k+\hdots + (x-1)^k,\ \ k\geq 2,$$
can be solved using solutions to the Pell equation~\cite{shaffer}, which is itseld a special case of norm equations of the form 
$$\mathcal{N}(\alpha) = 1.$$


\subsection{Practical computations in the quadratic case}

%L'algorithme du calcul le plus efficace à ce jour du groupe de classes d'idéaux $\Cl(\OK)$ d'un corps quadratique $K$ a été décrit 
%par Hafner et McCurley~\cite{hafner}. Il a ensuite considérablement été amélioré par l'emploi de techniques de crible empruntées 
%à la factorisation. Ainsi, l'état de l'art était dû à Jacobson qui a adapté avec succès le \og Multiple Polynomial Quadratic 
%Sieve\fg (MPQS) et le \og Self Initialization Quadratic Sieve\fg (SIQS) afin d'accélérer considérablement la phase de recherche 
%de relations . Outre l'amélioration des temps de calcul, ces méthodes ont permi le calcul du groupe de classe et du régulateur 
%de corps quadratiques de discriminant ayant 90 chiffres décimaux dans le cas imaginaire et 100 chiffres décimaux dans le cas réel.
The subexponential time algorithm for computing the ideal class group $\Cl(\OK)$  of a quadratic number field $K$ is due to 
Hafner and McCurley~\cite{hafner}. It was considerably improved by the use of sieving techniques borrowed from factorization. 
The 
state of the art was due to Jacobson who successfully adapted the ``multiple quadratic sieve'' (MPQS) and the ``self initialization 
quadratic sieve'' (SIQS) to significantly improve the search for relations in $\Cl(\OK)$. Besides enhancing the running time, 
these methods allowed the computation of the class group and fundamental unit of quadratic fields with a discriminant having 
repsectively 90 decimal digits in the imaginary case and 100 decimal digits in the real case.  


%J'ai proposé des améliorations à l'algorithme de Jacobson basé sur le SIQS. J'ai en particulier fait appel à la variation des grands 
%premiers~\cite{Lenstra2LP}, aux méthodes méthodes d'élimination gaussiennes structurées~\cite{cavallar} ainsi qu'aux tests de 
%friabilité simultanés dûs à Bernstein~\cite{bernstein}. Ces techniques se sont révélées efficaces. Elles permettent 
%une amélioration d'au moins un facteur 4 sur la même plateforme par rapport au SIQS classique de Jacobson. De même, j'ai réalisé 
%le calcul du groupe de classe et du régulateur pour des corps de nombres ayant un discriminant de 110 chiffres décimaux dans le 
%cas imaginaire comme dans le cas réel. Les améliorations concernant le cas imaginaires sont décrites dans~\cite{biasse_quad}, 
%tandis que celles concernant le cas réel, qui ont été réalisées en collaboration avec Jacobson à l'université de Calgary, se 
%trouvent dans~\cite{BiaJac10}.
I proposed improvements to Jacobson's SIQS algorithm. In particular, I used large prime variations~\cite{Lenstra2LP}, structured 
Gaussian elimination methods~\cite{cavallar}, as well as batch smoothness tests due to  Bernstein~\cite{bernstein}. These 
techniques proved themselves to be efficient. They allowed a significant run time improvement with respect to 
Jacobson's original SIQS method. In addition, I calculated the class group and the fundamental unit of number fields with 
a discriminant having 110 decimal digits in both the imaginary and the real case. The improvements concerning the imaginary case 
are described in~\cite{biasse_quad}, while these concerning the real case, which were obtained in collaboration with Jacobson at the
University of Calgary, can be found in~\cite{BiaJac10}.


%Mes travaux sur les corps quadratiques ont été distribués via le logiciel de calcul formel MAGMA~\cite{magma}. 
My work on quadratic number fields was distributed via the computer algebra software MAGMA~\cite{magma}.

\subsection{Practical computations in arbitrary degree}

%Les algorithmes décrits dans~\cite{biasseL13} sont basés sur le crible algébrique qui s'est révélé être efficace dans 
%la pratique pour la factorisation d'entiers de taille record. Afin d'étendre l'utilisation du crible au calcul du groupe 
%de classes d'idéaux, du régulateur et d'un système fondamental d'unités d'un corps de nombres de degré arbitraire, j'ai 
%implanté en collaboration avec Fieker à l'université de Sydney une recherche de relations similaire à celle du crible algébrique. 
%Cette méthode tire parti des améliorations les plus récentes du crible algébrique telles que le \og lattice sieving\fg, le 
%\og special-$q$\fg ainsi que des variations des grands premiers. Cette avancée permet une amélioration significative des 
%performances par rapport à la stratégie décrite dans~\cite{Buchmann}, tout particulièrement pour les petits degrés.
The algorithms I described in~\cite{biasseL13} are based on the number field sieve, which proved itself to be the most efficient 
algorithm for factoring large integers. To extend the use of sieving to ideal class group and unit group comptuation of 
arbitrary degree number fields, I implemented, in collaboration with Fieker at the University of Sydney, an algorithm 
for deriving relations similar to the number field sieve. This method uses the most recent improvements of the number 
field sieve such as the ``lattice sieving'' and the ``special-Q''. This breakthrough allows significant improvements 
in the performances with respect to the strategy described in~\cite{Buchmann}, especially for small degree number fields. 


%Afin de réduire la précision nécessaire au calcul du régulateur, nous développons avec Fieker une méthode basée 
%sur des approximations $p$-adiques plutôt que des approximations à virgule flottante ou fixe. L'emploi des $p$-adiques 
%permet notamment de ne pas subir de perte de précision à chaque manipulation d'une approximation rationnelle d'une valeur réelle. 
%Cette stratégie s'est révélée très efficace.
To reduce the precision required for computing the regulator, I used, in collaboration with Fieker, a method based on 
$p$-adic approximations rather than floating point approximations. The use of $p$-adics avoids loosing precision at each 
manipulation of a rational approximation of a logarithm embedding, which reveals itself very efficient in unit computation.


%Les améliorations concernant les corps de nombres de degré arbitraire seront, à l'instar du cas quadratique, distribués via le 
%logiciel de calcul formel MAGMA~\cite{magma}.
The improvements concerning arbitrary degree number fields are, as in the quadratic case, distributed via the computer algebra 
software MAGMA~\cite{magma}.

\subsection{Theoretical results}

%Jusqu'à présent, la meilleure complexité (heuristique) connue pour le calcul du groupe de classes d'idéaux, du régulateur et 
%d'un système d'unités fondamentales dans un corps de nombre de dimension fixée $n$ et de discriminant $\Delta$ était en 
%$L_\Delta(1/2 , O(1))$, où la fonction sous-exponentielle $L$ est définie par
%$$L_\Delta ( \alpha , \beta ) := e^{\beta (\log|\Delta|)^{1/3}(\log\log|\Delta|)^{2/3}}.$$
%Ce résultat, dû à Buchmann~\cite{Buchmann} est une généralisation de l'approche de Hafner et McCurley~\cite{hafner} qui ont 
%traité le cas quadratique. Il ne s'étend pas aux classes de corps de nombres de degré croissant vers l'infini, et ne mentionne 
%pas la précision à laquelle le régulateur est calculé.
Until now, the best (heuristic) known complexity for the computation of ideal class group, regulator and unit group of 
a fixed degree $n$ number field and of discriminant $\Delta$ was in $L_\Delta(1/2 , O(1))$, where the subexponential 
function $L$ is defined by 
$$L_\Delta ( \alpha , \beta ) := e^{\beta (\log|\Delta|)^{1/3}(\log\log|\Delta|)^{2/3}}.$$
This result, due to Buchmann~\cite{Buchmann}, is a generalization of the approach of Hafner and McCurley~\cite{hafner} who
treated the quadratic case. It doesn't extend to classes of number fields where the degree tends to infinity, and 
does not mention the precision of the regulator. 

%J'ai décrit~\cite{biasseL13} un algorithme pour le calcul du groupe de classes, du régulateur et d'un système d'unités 
%fondamentales dont la complexité heuristique dans certaines classes infinies de corps de nombres est en $L(1/3,O(1))$. 
%Cet algorithme est inspiré du travail de Enge et Gaudry~\cite{Enge} dans les jacobiennes de courbes $C_{a,b}$, dérivant lui même 
%de l'algorithme du crible algébrique~\cite{NFS} pour la factorisation de grands entiers. Ces classes infinies sont les premières 
%pour lesquelles le calcul de ces objets peut se faire en une meilleure complexité que $L(1/2,O(1))$. Dans~\cite{biasseL13}, 
%j'ai aussi analysé rigoureusement  la perte de précision engendée par le calcul du régulateur, indispensabe pour garantir la 
%précision de l'approximation calculée ainsi que l'exactitude des unités fondamentales. J'ai aussi adapté ces 
%résultats~\cite{biasseDLPL13} à la résolution du problème du logarithme discret dans le groupe de classes et du test de 
%principalité d'un idéal dans l'ordre maximal d'un corps de nombres, qui peuvent tous deux se résoudre en complexité 
%heuristique $L(1/3)$.
I described~\cite{biasseL13} an algorithm for computing the class group, the regulator and the unit group whose heuristic 
complexity for certain infinite classes of number fields is in $L(1/3,O(1))$. This algorithm is inspired from the work of 
Enge and Gaudry~\cite{Enge} on the Jacobian of $C_{a,b}$ curves, which is itself derived from the number field sieve~\cite{NFS}. 
These inifinite classes are the first for which the computation of these invariants can be done in a better (heuristic) 
complexity than $L(1/2,O(1))$. In~\cite{biasseL13}, I also rigorously adressed the loss of precision induced by the computation
of the regulator, which is an essential value to certify the class group and the unit group. I also adapted these 
results~\cite{biasseDLPL13} to the resolution of the discrete logarithm problem in the class group and the test of principality 
of an ideal in the ring of integers of a number field, which can both be solved in heuristic complexity  $L(1/3)$ for these 
classes of number fields.  


\section{Computer algebra}

%Étant donné un anneau $R$, et un $R$-module de dimension $n$, une tâche essentielle en calcul formel est le calcul d'une 
%base $b_1,\cdots,b_n$ jouissant de bonnes propriétés et telle que 
%$$M = R b_1 + \cdots + R b_n.$$
%Par exemple. dans le cas $R = \Z$, l'algorithme LLL~\cite{LLL} permet notamment de trouver une base de $M$ ayant de courts 
%vecteurs, permettant ainsi de faciliter la résolution de la recherche du plus court vecteur dans $M$, ou bien la recherche 
%du vecteur le plus proche dans $M$.

Given a ring $R$ and an $R$-module $M$ of dimension $n$, an essential task in computer algebra is the 
computation of $b_1,\cdots,b_n$ enjoying good properties and such that
$$M = R b_1 + \cdots + R b_n.$$
For example, in the case $R = \Z$, the LLL algorithm~\cite{LLL} allows to find a basis of $M$ having short vectors, thus 
facilitating the search for the shortest vector of $M$. This algorithm has a lot of applications in lattice-based 
cryptology. Another typical example is the Hermite Normal Form (HNF) computation of a system of generators of the
$\Z$-module $M$ of the relations in a group $(G,*)$. Let $(g_1,\cdots,g_n)$ be generators of $G$, each relation of the 
form 
$$g_1^{e_1}*\cdots*g_n^{e_n} = 1_G,$$
corresponds to a vector $(e_1,\cdots,e_n)\in M$. The computation of an HNF basis of $M$ consists of unimodular operations 
on the matrix representing the generators of $M$ leading to a triangular form. This occurs in particular during the 
computation of the structure of $G$, and the computation of discrete logarithms in $G$. 
\subsection{Hermite Normal Form in $\Z$}

Putting a matrix in triangular form is often necessary in the context of algorithmic number theory and cryptology. It can 
be applied to system solving, computing the structure of a finite group or solving the discrete logarithm problem. In particular,
 the Hermite normal form (HNF) is a lower triangular form that can be used used for computing finite 
group structures and solving the discrete logarithm problem. Few implementations of HNF algorithms for matrices over $\Z$ are 
available. The 
fastest one is indisputably the one implemented by Steel in Magma~\cite{magma}, but it is unfortunately not freely available, nor
open source or even published. 
%La mise sous forme triangulaire d'une matrice intervient souvent dans le contexte de la théorie algorithmique des nombres et de la 
%cryptologie. Cela peut s'appliquer à la résolution d'équations, au calcul de la structure d'un groupe fini ou encore 
%à la résolution du problème du logarithme discret. En particulier, la forme normale de Hermite (HNF) d'une matrice à coefficients 
%dans $\Z$ permet de trouver une base appropriée du $\Z$-module des relations d'un groupe fini. Cette base HNF est utilisable pour 
%le calcul de la structure du groupe fini en question, ainsi que la résolution du problème du logarithme discret. Peu 
%d'implémentations efficaces d'algorithmes de mise sous forme HNF de matrices sont disponibles, et le plus rapide, distribué via 
%le logiciel de calcul formel Magma~\cite{magma} n'est malheureusement ni open source, ni même publié dans la littérature.

In collaboration with the CASYS team from the Jean Kunzmann laboratory (University of Grenoble), I implemented 
efficient algorithms for computing the HNF of an integer matrix. Our strategy was to take into account the specificities of the 
matrices that are processed during index calculus algorithms such as discrete logarithm computation or group structure 
computation. Indeed, on the one hand these matrices may have large dimensions, but on the other hand they are usually sparse 
with coefficients of small size , and their Hermite Normal Form usually have a small non trivial part (the essential part). 
These specificities were not exploited by the current available algorithms. We distributed our work through the open source 
linear algebra C++ library Linbox~\cite{linbox}. It includes various algorithms for random matrices and an original bloc 
algorithm dedicated to matrices from index calcul which is based on the ideas of~\cite{JacobsonHNF} .


%En collaboration avec l'équipe CASYS du laboratoire Jean Kunzmann à Grenoble, j'ai implanté des algorithmes efficaces permettant 
%la mise sous forme HNF d'une matrice sur les entiers. Notre angle d'attaque a été de prendre en compte les spécificité des matrices 
%traitées dans les algorithmes de calcul d'index tels que la résolution du logarithme discret ou la recherche de la structure d'un 
%groupe. En effet, d'un côté ces matrices peuvent avoir de grandes dimensions, mais de l'autre, elles sont souvent creuses, avec 
%des coefficients de petite taille et  leur forme de Hermite a seulement un petite partie non triviale (partie essentielle). Ces 
%spécificités ne sont pas exploitées par les algorithmes disponibles à l'heure actuelle. Nous avons diffusé via le projet open 
%source Linbox~\cite{linbox} une série d'algorithmes pour le calcul de HNF, dont l'implantation originale d'un algorithme par blocs 
%basé sur l'algorithme décrit dans~\cite{JacobsonHNF}.

\subsection{Reduced basis of an $\OK$-module}

The construction of a good basis of an $\OK$-module, where $K$ is a number field and $\OK$ its ring of 
integers, has recently received a growing interest from the cryptographic community. Indeed, $\OK$-modules 
occur in lattice-based cryptography~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, where 
cryptosystems rely on the difficulty to find the shortest element of a module, or solving the closest 
vector problem. 
%La construction d'une bonne base pour un $\OK$-module où $K$ est un corps de nombres et $\OK$ son anneau des 
%entiers a reçu dernièrement un attention considérable de la part de la communauté scientifique. En effet, les 
%$\OK$-modules interviennent en cryptographie basée sur les réseaux~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, 
%où la sécurité des cryptosystèmes repose sur la difficulté de trouver le vecteur le plus court, ou le vecteur le
%plus proche.

The computation of a Hermite Normal Form (HNF)-basis was generalized to $\OK$-modules by Cohen~\cite[Chap. 1]{cohen2}. 
His algorithm returns a basis that enjoys similar properties as the HNF of a $\Z$-module. A 
modular version of this algorithm is conjectured to run in polynomial time, although this statement is not 
proven (see last remark of~\cite[1.6.1]{cohen2}). In addition, Fieker and Stehl{\'e}'s recent algorithm for computing a 
sized-reduced basis relies on the conjectured possibility to compute an HNF-basis for an $\OK$-module in polynomial 
time~\cite[Th. 1]{stehle_fieker_LLL}. In collaboration with Fieker, I ellaborated a modified version of Cohen's algorithm 
that calculates the HNF of an $\OK$-module~\cite{pseudo_HNF}. It is the first polynomial time algorithm for this task.
%Le calcul de la HNF a été généralisé aux $\OK$-modules par Cohen~\cite[Chap. 1]{cohen2}. Son algorithme retourne une base 
%ayant des propriétés similaires à celles de la HNF sur $\Z$. Cohen a conjecturé que la version modulaire de cet algorithme 
%avait une complexité polynomiale, mais aucune preuve n'est disponible dans la littérature. De plus, Fieker et Stehl{\'e} ont 
%récemment publié un algorithme analogue à l'algorithme LLL pour le calcul d'une base réduite d'un $\OK$-module dont le temps 
%de calcul repose sur la polynomialité de l'algorithme de Cohen\cite[Th. 1]{stehle_fieker_LLL}. En collaboration avec Fieker, 
%j'ai élaboré une version modifiée de l'algorithme de Cohen dont nous avons analysé la complexité~\cite{pseudo_HNF}. C'est le 
%premier algorithme polynomial de calcul de la HNF d'un $\OK$ module. 


\section{Cryptology and coding theory}

\subsection{Stream ciphers}

During the eSTREAM competition, Bernstein described a family of stream ciphers called 
Salsa/$i$ (see~\cite{salsa20}), where $i$ denotes
the number of rounds used. Berstein emphasized the use of 8, 12 and 20 rounds. Crowley~\cite{crowley} was the first to present an 
attack on Salsa. His differential cryptanalysis was valid for 5 rounds. The same year, I presented, in collaboration with Berbain, 
Fisher, Meier and Robshaw (FHNW and Orange labs)~\cite{Orange_salsa} an attack valid for 6 and 7 rounds of the stream cipher Salsa. 
Since then, the best cryptanalysis published on Salsa is valid for 8 rounds~\cite{Salsa_8}. It is therefore safe to say that the 
family of ciphers Salsa
represent a strong computational challenge. 
%Pendant la compétition eSTREAM, Bernstein a décrit une famille de stream ciphers appelée Salsa/$i$ (voir~\cite{salsa20}), où 
%$i$ dénote le nombre de tours utilisés. Bernstein a mis l'accent sur l'usage de 8, 12, 20 tours. Crowley~\cite{crowley} a été le 
%premier à présenter une attaque sur la famille de stream ciphers Salsa. Sa cryptanalyse différentielle fonctionne sur 5 tours. La 
%même année, j'ai présenté, en collaboration avec Berbain, Fisher, Meier et Robshaw (FHNW et Orange labs)~\cite{Orange_salsa}, une 
%attaque valide pour 6 et 7 tours du stream cipher Salsa. Depuis, la meilleure cryptanalyse publiée sur Salsa est valide sur 
%8 tours~\cite{Salsa_8}. Salsa est donc bien une famille de stream ciphers intéressante, repoussant les limites des techniques 
%de cryptanalyse symétrique.   

\subsection{Discrete logarithm}

%J'ai réalisé des implantations d'algorithmes pour la résolution du problème du logarithme discret dans le groupe de classes 
%d'un ordre quadratique, et de la résolution du problème de principalité d'idéaux dans un ordre quadratique à partir de 
%résolution de systèmes linéaires diophantiens. Ces implantations comprenant 
%des améliorations pratiques significatives par rapport au précédant étant de l'art, j'ai entrepris, en collaboration avec 
%Jacobson et Silvester à l'université de Calgary, une nouvelle étude de la sécurité des cryptosystèmes reposant sur la 
%difficulté de ces problèmes dans le cas quadratiques~\cite{BiaJacSil10}. La conclusion de ce projet a été la nécessité de 
%relever la taille des clefs par rapport aux précédantes recommantations~\cite{HMiq}.
I realized implementations of algorithms for solving the discrete logarithm problem in the ideal class group of a quadratic 
order, as well as solving the principal ideal problem from solutions to systems of Diophantine linear equations. These 
implementations include significant practical improvements over the previous state of the art. I did, in collaboration with 
Jacobson and Silvester (University of Calgary), a new study of the security of cryptosystems based on the difficulty of 
these problems in the quadratic case~\cite{BiaJacSil10}. We concluded that there was a necessity to increase the size of the 
keys with respect to the previous recommantations~\cite{HMiq}.

\subsection{List decoding of number field codes}
In his thesis, Guruswami~\cite[Chap. 7]{guruswami_phd} described a general framework for list decoding residue codes. These codes 
are defined by a ring $R$ and coprime ideals $I_1,\cdots,I_n$. The encryption function is given by
\[   \left. \begin{array}{cccc}
      &   R & \longrightarrow  & R/I_1\times \cdots \times R/I_n \\
    c:&    m & \longmapsto & (m\bmod I_1,\cdots ,m \bmod I_n) \end{array} \right. . \]
In the case where $R$ is the univariate polynomial ring over a finite field, and the $I_i$ are generated by polynomials $p_i$, the message 
is transmitted via the evaluation of the $p_i$ at a point, which is precisely the definition of Reed-Solomon codes. This approach 
allows to unify the decoding of Reed-Solomon codes, their generalization the algebraic-geometric codes~\cite{wasserman}, and the 
Chinese remainder codes~\cite{guruswami_sudan_soft_CRT} where the message is the residue of an integer modulo a tuple of $n$ prime
numbers.
%Dans sa thèse, Guruswami~\cite[Chap. 7]{guruswami_phd} a décrit une stratégie générale pour décoder en liste des codes à base de 
%résidus. Ces codes sont définis par un anneau $R$ et des idéaux premiers entre eux $I_1,\cdots,I_n$. L'encodage est donné par 
%\[   \left. \begin{array}{cccc}
%      &   R & \longrightarrow  & R/I_1\times \cdots \times R/I_n \\
%    c:&    m & \longmapsto & (m\bmod I_1,\cdots ,m \bmod I_n) \end{array} \right. . \]
%Dans le cas où $R$ est l'anneau des polynômes à une indéterminée sur un corps fini, et les $I_i$ sont générés par des polynômes 
%$p_i$, le message $m$ est transmis via l'évaluation des $p_i$ en $m$, ce qui est précisément la définition des codes de Reed-Solomon.
%Cette approche permet d'unifier le décodage des codes de Reed-Solomon, leur généralisation les codes 
%algébriques-géométriques~\cite{wasserman} et les codes CRT~\cite{guruswami_sudan_soft_CRT} pour lesquels le message est une 
%collection de résidus modulo un $n$-uplet de nombres premiers.  

The case where $R$ is the ring of integers of a number field and the $I_i$ are prime ideals $\p_i\subset R$ was studied independantly
by  Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}. They exhibited classes of number fields with good properties,
but failed at providing a decoding algorithm. In collaboration with Quintin (\'{E}cole Polytechnique), I described the first polynomial time algorithm for 
decoding codes based on number fields~\cite{biasse_codes}. We showed that we could achieve the same decryption bounds as for the 
Chinese Remainder Codes..
%Le cas où $R$ est l'anneau des entiers d'un corps de nombres et les $I_i$ sont des idéaux premiers $p_i\subset R$ a été étudié 
%indépendamment par Lenstra~\cite{lenstra_nb_fld} et Guruswami~\cite{guruswami_nb_fld}. Ils ont mis en évidence des classes de 
%corps de nombres jouissant de bonnes propriétés, mais n'ont pas décrit d'algorithme de décodage. En collaboration avec Quintin, j'ai 
%décrit le prmier algorithme polynomial de décodage en liste pour les codes basés sur les corps de nombres~\cite{biasse_codes}. Nous 
%avons montré que nous pouvions atteindre la borne de Johnson pour le décodage en liste, ce qui est similaire à l'état de l'art pour 
%le cas plus simple des codes CRT.


\bibliography{travaux}

\end{document}